package com.springboot.demo.sort;

/**
 * 快速排序，不稳定（选取的基数决定排序效率）
 *
 * <p>
 * 算法思想：
 * 1、选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
 * <p>
 * 2、递归的将p左边和右边的数都按照第一步进行，直到不能递归
 * <p>
 * 时间复杂度：o(nlogn)
 * 空间复杂度：o(nlogn)
 *
 * @author supu
 * @date 2019-12-12 14:02
 **/
public class QuickSort {
    /**
     * @param a     待排序数组
     * @param start 开始位置
     * @param end   结束位置
     */
    public static void quickSort(int[] a, int start, int end) {
        if (start < end) {
            // 选取第一个数作为基数
            int baseNumber = a[start];
            // 大于基数的位置
            int i = start;
            // 小于基数的位置
            int j = end;

            do {

                while (i < end && a[i] < baseNumber) {
                    // 找出比基数大的位置
                    i++;
                }

                while (j > start && a[j] > baseNumber) {
                    // 找出比基数小的位置
                    j--;
                }

                // 两者位置还没有交叉错开
                if (i <= j) {
                    // j 位置的数比i位置的数小，交换两者位置的数
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    // 交换之后，i位置+1，j位置-1
                    i++;
                    j--;
                }

            } while (i <= j);

            // 此时以基数为准，左边的数都比基数小，而右边的数都比基数大

            if (start < j) {
                // 都比基数小的数
                quickSort(a, start, j);
            }

            if (end > i) {
                // 都比基数大的数
                quickSort(a, i, end);
            }

        }
    }

    public static void quickSort1(int[] a, int start, int end) {
        /*if(start < end){
            int base = a[start];
            int i = start;
            int j = end;
            do {
                while (i < end && a[i] < base){
                    i++;
                }

                while (j > start && a[j] > base){
                    j--;
                }

                if(i <= j){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    i++;
                    j--;
                }

            }while (i <= j);

            if(j > start){
                quickSort1(a, start, j);
            }

            if(i < end){
                quickSort1(a,i,end);
            }
        }*/
        if (start < end) {
            int base = a[start];
            int i = start;
            int j = end;
            do {
                while (i < end && a[i] < base) {
                    i++;
                }
                while (j > start && a[j] > base) {
                    j--;
                }

                if (i <= j) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);

            if(j > start){
                quickSort1(a, start, j);
            }

            if(i < end){
                quickSort1(a, i, end);
            }
        }
    }
}
